/**
 * 239. 滑动窗口最大值
 * https://leetcode-cn.com/problems/sliding-window-maximum/
 */
const { displayBaseArray } = require('../../libs/public');

let queue;
let bottom;
let top;

/**
 * @param {number} newIndex
 * @param {number} minIndex
 * @param {number[]} nums
 */
function push(newIndex, minIndex, nums) {
  while (top >= bottom && queue[bottom] < minIndex) {
    bottom += 1;
  }
  while (top >= bottom && nums[newIndex] >= nums[queue[top]]) {
    top -= 1;
  }
  top += 1;
  queue[top] = newIndex;
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
function maxSlidingWindow(nums, k) {
  const result = new Array(nums.length - k + 1).fill(0);
  queue = new Array(nums.length).fill(0);
  bottom = 0;
  top = -1;
  for (let i = 0; i < k; i += 1) {
    push(i, 0, nums);
  }
  result[0] = nums[queue[bottom]];
  for (let i = 1; i < result.length; i += 1) {
    push(i + k - 1, i, nums);
    result[i] = nums[queue[bottom]];
  }
  return result;
}

console.log(displayBaseArray(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)) === '[3,3,5,5,6,7]');
console.log(displayBaseArray(maxSlidingWindow([1], 1)) === '[1]');
